package reviewAlgorithms.math;

public class CountPrimes {
    public static void main(String[] args) {
        int n = 1500000;
        System.out.println(countPrimes(n));
    }
    public static int countPrimes(int n) {
        if (n < 1){
            return 0;
        }
        boolean[] nums = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!nums[i]){
                int times = 2;
                while (i * times < n){
                    nums[i * times] = true;
                    times ++;
                }
                count ++;
            }
        }
        return count;
    }
}
